package com.ShangGuiGu.FindAlgorithm;

/**
 * @authoer zsj
 * @date 2022/3/3 12:29
 * 又称黄金分割算法
 * 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
 */
public class 斐波那契数列算法 {

    public static void main(String[] args) {

        int[] fib = fib();
        for (int i : fib) {
            System.out.print(i+",");
        }
    }

    //数列最大长度
    public static int maxSize = 20;

    /**
     * 得到一个斐波那契数列
     *
     * @return
     */
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 斐波那契查找算法
     * 前提 数组是有序的且是一个斐波那契数列
     * @param fib  斐波那契数列
     * @param target 寻找的目标值
     * @return 返回对应下标  没找到返回-1
     */
    public static int fibSearch(int[] fib,int target) {
        int begin = 0;
        int end = fib.length -1;
        int k = 0;//表示斐波那契分割数值的下标
        int mid = 0;//存放mid
        int f[] = fib();//获取斐波那契数列
        //获取到斐波那契分割数值的下标


        return -1;
    }


}
